package com.platform.modules.alg.alglib.p65;

public class P65 {
    private final int maxn = 10000;
    int n;
    int a[] = new int[maxn];
    int c[] = new int[maxn];
    int s[] = new int[maxn];
    public String output = "";

    // c[i]的区间长度
    int lowbit(int i) {
        return (-i) & i;
    }

    // a[i]加上z
    void add(int i, int z) {
        for (; i <= n; i += lowbit(i)) // 直接后继，即父亲i+=lowbit(i)
            c[i] += z;
    }

    // 求前缀和a[1]..a[i]
    int sum(int i) {
        int s = 0;
        for (; i > 0; i -= lowbit(i)) // 直接前驱 i-=lowbit(i);
            s += c[i];
        return s;
    }

    // 求区间和a[i]..a[j]
    int sum(int i, int j) {
        return sum(j) - sum(i - 1);
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        String[] num = line[1].split(" ");
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(num[i - 1]);
            add(i, a[i]);//加入树状数组
        }
        int x1, x2;
        String[] query = line[2].split(" ");
        x1 = Integer.parseInt(query[0]);
        x2 = Integer.parseInt(query[1]);
        output += sum(x1) + "\n";
        output += sum(x1, x2) + "";
        return output;
    }
}
